package demo1;

import com.sun.source.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;

public class MyTree {
    //创建二叉树的节点
static   class TreeNode {
    public TreeNode(int data){
        this.data = data;
    }
    TreeNode  left;    //树的左节点
    TreeNode  right;  //树的右节点
    int data;               //数据
}

//树的根节点
    TreeNode root;
//构造方法
public MyTree() {
    TreeNode A = new TreeNode(1);
    TreeNode B = new TreeNode(2);
    TreeNode C = new TreeNode(3);
    A.left = B;
    A.right = C;
    this.root = A;
}
    // 1. 获取树中节点的个数
   public int size(TreeNode root){
        //不使用计数器，而是将临时变量保存在方法中
       if(root ==null){
           return 0;
       }
      return size(root.left)+size(root.right)+1;
    }

//  2.获取叶子节点的个数

public     int getLeafNodeCount(TreeNode root){
    //采用递归的思想：
    if(root == null){ // 当一个节点的一个左子树（右子树）为空，或者树为空时，会出现这种情况
        return 0;
    }
    if(root.left ==null&&root.right== null){
        return  1 ;
    }
    int size = getLeafNodeCount(root.left)+getLeafNodeCount(root.right);

    return size;
}
// 3.获取第K层节点的个数
public    int getKLevelNodeCount(TreeNode root,int k){
    if(root == null){
        return 0;
    }
    if(k ==1&&root !=null){
        return 1;
    }
     return  getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
}
// 4. // 获取二叉树的高度
public    int getHeight(TreeNode root){
    if(root == null){
        return 0;
    }

    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);

    return leftHeight>rightHeight ? leftHeight+1:rightHeight+1;
}
// 5 . // 检测值为value的元素是否存在
public TreeNode Find(TreeNode root, int val){
      //实现思想:遍历二叉树判断
    //采取前序遍历
    if(root == null){
        return null;
    }
    if(root.data == val){
        return root;
    }

    TreeNode treeNode1 =  Find(root.left,val);
    if(treeNode1 !=null){
        return treeNode1;
    }

   TreeNode treeNode2 =   Find(root.right,val);
   if(treeNode2 !=null){
       return treeNode2;
   }
   return  null;

}
// 6 . 层序遍历
 public   void levelOrder(TreeNode root){
        if(root == null){
            return ;
        }
     LinkedList  <TreeNode> queue = new LinkedList();   //创建队列
     queue.offer(root);
       while (!queue.isEmpty()) {

           //打印队列中的节点
           TreeNode cur = queue.poll();
           System.out.println(cur.data);
           //然后将本节点左节点与右节点放入队列中
           if (cur.left != null) {
               queue.offer(cur.left);
           }
           if (cur.right != null) {
               queue.offer(cur.right);
           }
       }
     }
 }
// 7. 按行进行层序遍历


// 8. 判断一棵树是否是完全二叉树
 public      boolean isCompleteTree(TreeNode root) {
   /*  //代码1 ：
    if(root == null){
         return true ;
     }
     LinkedList  <TreeNode> queue = new LinkedList();   //创建队列
     queue.offer(root);
     while (!queue.isEmpty()) {

         //打印队列中的节点
         TreeNode cur = queue.poll();
         if(cur == null) {
           //如果队列中出来了null，判断队列中的其他元素是否为空
             while (!queue.isEmpty()) {
                TreeNode cur2 = queue.poll();
                if(cur2 != null) {
                    return false;
                }
             }
             return true;
         }
         //然后将本节点左节点与右节点放入队列中,即使是null也要放进队列中去
             queue.offer(cur.left);
             queue.offer(cur.right);
     }
*/
     //代码2 ：
     if(root == null){
         return true ;
     }
     LinkedList  <TreeNode> queue = new LinkedList();   //创建队列
     queue.offer(root);
 while (!queue.isEmpty()) {
     TreeNode cur1 = queue.poll();
     if (cur1 != null) {
         queue.offer(cur1.left);
         queue.offer(cur1.right);
     } else {
         break;
     }
 }
     while (!queue.isEmpty()) {
         TreeNode cur2 = queue.pop();
         if(cur2 !=null) {
             return false;
         }
     }
  return true;
 }















 }


































}
